package club.vann.nowcoder;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <p>难度：Medium</p>
 * <p>题目：最常无重复子串</p>
 * <p>描述：给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。
 * 示例1
 * 输入
 * 复制
 * [2,3,4,5]
 * 返回值
 * 复制
 * 4
 * 示例2
 * 输入
 * 复制
 * [2,2,3,4,3]
 * 返回值
 * 复制
 * 3
 * 备注:
 * 1 \leq n \leq 10^51≤n≤10
 * 5</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-20:18:06:06
 */
public class NC41 {
    public static void main(String[] args) {
        NC41 nc41 = new NC41();

        System.out.println("Result["+TestCase.ANS+"] : " + nc41.maxLength(TestCase.ARR));
        System.out.println("Result["+TestCase.ANS1+"] : " + nc41.maxLength(TestCase.ARR1));
        System.out.println("Result["+TestCase.ANS2+"] : " + nc41.maxLength(TestCase.ARR2));
        System.out.println("Result["+TestCase.ANS3+"] : " + nc41.maxLength(TestCase.ARR3));
    }

    /**
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        int ans = 0;
        // 记录窗口中出现数字的个数
        Map<Integer, Integer> map = new HashMap<>();
        int len = arr.length;
        int left = 0, right = 0;
        while(right < len) {
            // 需要进入窗口的数字
            int in = arr[right];
            // 加入当前数字会导致重复
            if(map.containsKey(in)) {
                // 计算结果
                ans = Math.max(ans, right-left);
                // 找到重复元素首次出现的位置
                int index = map.get(in);

                // 清空
                for(int i = left; i <= index; i ++) {
                    map.remove(arr[i]);
                }
                left = index+1;
            }

            map.put(in, right);
            right ++;
        }
        ans = Math.max(ans, right-left);
        return ans;
    }

    static class TestCase {
        public static int ANS = 4;
        public static int[] ARR = {2,3,4,5};

        public static int ANS1 = 3;
        public static int[] ARR1 = {2,2,3,4,3};

        public static int ANS2 = 5;
        public static int[] ARR2 = {1,2,3,4,1,2,3,4,5};

        public static int ANS3 = 0;
        public static int[] ARR3 = {1988,10036,13287,24377,29106,8933,9124,14803,28081,28614,19887,4078,23539,2956,7669,11918,25334,6672,8961,15335,23223,29613,29389,22745,30755,29417,20951,31671,19662,17752,20600,26700,28391,17342,21105,26912,23916,5492,13511,11767,29850,8973,1490,29595,1704,7224,912,22747,27828,5352,21567,1236,9214,32179,11562,623,19284,31608,23491,29995,5325,25157,25842,2845,32698,22392,11949,20533,28378,24356,26569,18114,28365,22710,8719,26936,16587,11992,21139,31025,32150,16021,11329,16307,25773,14782,2233,8881,11203,2189,21341,13268,25199,28297,10919,7291,15909,30377,11201,2816,25189,27324,7247,1341,31026,23048,26255,17486,12230,29490,7077,32153,27524,13662,28720,15628,19246,15510,26401,13478,18520,11632,7885,9529,3357,1003,29761,17518,21008,18843,28885,17417,22645,30470,13828,24174,21682,1101,23418,3172,23808,27919,29551,18458,12390,11146,10548,360,27112,28419,11787,10070,29692,4456,26684,27362,20541,4149,6245,7934,1891,3220,26898,23001,21875,5832,7309,15199,26163,18635,19704,32003,13793,29750,29336,11964,27172,26466,9332,17741,14147,3533,18207,24010,9621,28607,7634,23128,19257,21805,29117,15412,19974,4061,17311,24311,16837,12491,15253,31000,13982,11468,19247,1458,3025,13425,13769,31623,23207,17198,29465,30022,3495,10683,8196,12041,30732,6075,29110,32034,375,26780,24305,8215,14818,14270,29605,6635,27093,32727,706,26783,29404,18838,10826,18937,5176,11654,23978,27780,26581,11574,27210,12760,11132,10135,10851,26139,10826,27813,23057,4296,23137,13385,17065,17071,733,31870,12364,1342,32266,4788,26044,20222,27604,19569,623,8544,26750,13118,3810,13242,7063,10177,9008,20365,13098,16423,23523,16905,7990,26053,4362,1747,8541,30206,908,4101,1248,27239,29883,20343,4811,19497,23596,25917,5741,30375,12231,6000,1547,28001,29210,30514,9174,18712,31474,22252,11033,52,11821,30170,23991,3682,5322,1226,1493,16257,3138,26656,16340,8639,27,23326,8322,25343,25018,22626,2961,7551,21113,27568,20040,22455,13305,20722,21112,15236,4794,1149,32178,18565,7912,10390,4279,1477,10104,25653,6960,30363,19316,7945,22431,22223,21907,16059,918,25086,30221,18807,2087,10816,20141,4521,1691,16903,1320,20228,7526,15691,20397,18633,31067,19940,12221,30022,1821,32567,20285,12957,22742,21780,13258,31942,5163,20959,15436,17623,31855,10222,7374,19843,27926,6707,19597,12513,22637,20507,6734,29551,7817,8373,23285,18519,20605,6423,26196,27377,13265,16894,22081,12680,6703,26804,15339,15713,24926,28471,16238,27641,12149,26519,23972,28047,16200,32416,14398,9442,20775,31161,11284,13372,5064,19468,8634,23471,6529,1767,19540,3231,11706,10594,19115,22145,7843,4931,24192,4321,20258,7966,11808,26282,9488,10177,17464,9890,10148,31951,16875,32052,25135,2730,30498,31602,24330,14742,21795,3930,20173,18460,28518,20824,12226,9389,32419,19213,2458,2696,6704,6991,4446,26078,7050,7025,18856,17203,24626,27076,29458,19975,23994,32093,24815,8886,15391,10009,1593,30621,27225,9183,20171,24958,24881,9253,6352,14117,2131,27830,25212,22604,29092,29874,32762,23485,24277,9430,28069,26806,17721,7165,4730,16273,17363,7399,1741,13732,16308,2362,13116,10343,6788,3526,23522,11220,14174,25613,27597,30740,16865,19715,5297,23127,27523,10514,5853,11524,4905,20833,17775,6930,2805,5718,6852,12981,28767,1882,28979,2878,19080,26588,13307,572,25290,30104,7289,21480,2964,25625,20383,4800,18805,12668,28577,17009,4726,14456,30193,6650,6061,9115,26990,12559,19727,9686,17625,7355,9094,7228,8584,16202,10564,32007,31326,20326,1110,14300,6906,23168,31612,27472,3887,18034,312,5034,9908,5730,29989,5866,24861,30441,3978,21003,22026,21876,11055,2950,28063,1771,24943,28439,32052,16785,11407,30403,7245,28204,1102,25882,17868,5221,10429,13498,6501,26225,3921,8468,20819,12273,9783,11379,16457,11287,25063,18234,27564,1803,18684,31852,5631,3725,29251,18290,19871,21979,10514,30489,21424,20693,11227,16859,28503,10847,14592,28511,297,23047,24041,15171,27364,15592,15445,21784,8029,13773,14829,8622,28346,6298,19999,8594,25313,25832,25129,8406,16433,5104,30580,5136,32367,32170,2084,18085,19971,6454,21997,15944,32100,7290,6952,30653,21201,16141,21030,24803,11842,9299,1732,13297,1950,12522,26175,6144,7470,20293,330,10954,26194,26519,29790,22449,7794,3827,27218,8195,31800,12721,11563,14460,26876,15635,14645,8204,19584,3113,1619,5083,16606,7153,31635,1163,17086,19139,16645,28861,12748,9964,25550,18646,13674,4250,120,16387,22945,13048,26508,11898,30814,6297,28771,26883,17115,24346,28217,12727,32603,19971,31619,9736,20250,21743,3970,19970,4228,13549,4633,12497,12709,22821,25052,4738,1761,8895,105,16142,31205,11264,22779,1684,9437,18102,21820,20198,11751,14807,13403,24135,30408,613,22623,17267,29919,7060,32187,32480,17751,4655,4386,20804,20896,26424,6044,21335,6175,1487,23770,15066,27940,20564,23494,28888,18461,2256,5471,23852,28938,6289,18884,2883,8753,31509,18318,3107,29203,20522,17763,14764,6558,22866,31177,16158,27300,26220,25911,2780,2700,30097,626,3440,17736,2621,20759,27086,3207,32687,28275,31453,30507,23186,12443,21043,21757,24028,30649,5152,10911,26359,10661,21743,10691,21791,2997,23400,31131,11,28373,27802,25488,463,25050,1239,14391,22529,24083,8703,129,8218,8737,770,20274,29472,12041,160,18068,9346,7048,25459,9836,26692,12711,23344,30253,9307,2702,31530,8044,29019,7325,24599,3220,3663,28601,25367,8155,19432,27620,32242,5748,13019,30225,17569,11270,27012,20278,6161,4702,7375,27042,30243,4449,28760,10385,2807,25412,14801,15870,26474,8447,2981,6840,221,21246,21210,9400,24121,31258,3132,10162,5679,9417,21688,13290,709,25745,22790,24393,19982,14275,26763,7344,15416,15205,12157,7564,22221,14704,23624,29099,23858,26428,13360,22862,7796,26680,23352,32127,8259,26846,21315,676,14143,26086,30330,10581,29811,29626,28909,29035,3103,6699,32125,29529,6587,6242,27129,25536,25912,9497,9863,30013,3465,32523,25670,3206,15458,25000,1841,31413,18240,12814,28487,12771,25001,30773,23785,10233,17589,30825,29827,23491,28621,254,9582,12358,26291,16447,30741,4692,4290,13991,1879,7261,7544,6484,10541,11400,4657,14520,2701,8450,25909,16274,17038,11926,18933,24092,8396,1407,4754,13702,15118,14458,19103,6052,32294,6687,28456,28388,17945,1136,26611,25218,16768,16051,9733,2815,9262,30077,2920,19151,27923,30992,44,8018,17248,13798,22700,32261,12012,7054,28947,4602,12247,26039,8734,28037,31085,31627,29475,1081,21581,22846,11602,274,27594,14310,13371,19700,2705,26509,18320,22868,2700,3972,4652,821,31751,18683,10837,8791,18450,18383,26430,6315,21030,1443,12240,30217,23819,9010,9898,1061,14072,29667,22375,20160,28925,26527,18719,31771,9630,18143,6704,2481,4801,29961,2366,16677,2762,11516,3960,31098,260,27625,28701,30850,13635,32358,24895,2201,17095,25533,12744,5779,5732,31626,4282,27634,4064,12677,22971,22876,21149,7068,2768,25933,2423,15941,18281,21258,8688,27410,3230,5590,17035,28037,31416,1127,117,31271,22515,24731,6250,5076,12418,1896,11991,23385,14292,23825,23356,32065,20246,18848,725,12779,21753,22928,18041,992,8885,22218,1986,20580,23118,28115,18798,13899,27157,13123,28421,26382,26995,7545,8124,3614,13026,18061,20634,17016,24380,2694,14809,13946,1592,21965,15247,6645,26673,14306,30094,25219,25898,3662,5768,28187,25872,23513,9847,13282,5438,8188,20539,30532,8007,17049,28293,12612,15599,26602,24565,9232,19834,16568,26239,19673,20522,10957,5651,10209,26627,13739,5757,31446,19665,24446,15498,6494,19820,7760,15980,22515,18235,2428,1887,8433,14071,14181,28301,24557,18097,9063,21807,14153,32023,12302,28662,13317,29171,6534,16297,29656,11252,27731,32015,29056,2993,21570,31759,27478,26603,22432,18966,6181,16146,21161,3001,7740,8715,18243,23964,194,15409,21741,15506,30538,7322,27890,14597,25511,9371,5858,31129,23042,16270,22850,20748,28458,18386,6787,27489,16682,15636,3633,22077,28193,12237,621,26769,27982,1548,8605,19833,32363,32118,31842,13924,9020,3723,28619,30838,22375,5419,15304,6442,31366,25176,24033,3644,8315,6973,1063,13510,15363,2415,11371,17321,22415,16500,17327,15662,20559,15490,23002,9197,18319,24200,15792,30446,15942,26995,5376,14607,3820,25770,17695,1957,14733,2010,16278,1126,13852,5113,1816,5767,16649,15749,183,18209,22037,3085,25943,15577,19814,21235,26466,6848,20182,10096,24765,18040,3985,30680,7419,22937,3551,10272,5073,16978,16190,22429,10186,22356,25780,13326,15676,25323,31075,32221,15739,26990,28510,8610,23116,11994,11963,2793,9629,16314,2794,5173,20851,330,8773,14405,11299,3291,23527,26773,11461,23161,30658,11560,9190,32460,25836,29061,25725,60,21050,8960,31008,1880,11536,1082,14712,28281,631,23019,21491,29858,30320,21727,8120,6059,17801,23871,19168,22943,1197,8978,14563,30050,4928,6147,9552,18071,29548,13925,24258,26816,31925,14708,11791,20903,7380,10974,15810,27390,6850,27010,5580,28482,4115,3447,32630,3557,3205,19792,26010,6827,6105,18590,1299,19541,1505,23479,370,20093,20699,24758,12786,10945,28157,451,15023,19747,20561,149,17938,10160,3523,5940,29328,14688,23161,22020,18580,31806,20066,8959,19641,32456,10514,15938,573,11417,1997,28619,29107,2629,16865,17025,2039,26757,24377,28788,24935,21140,23856,25703,21840,15320,13731,29836,21927,12485,23626,14990,30458,3839,9800,11476,13477,2238,20480,23813,17737,30583,5419,32711,4986,16825,3879,8653,11960,22613,19858,11792,18593,3777,23832,10588,4708,21182,12425,18191,3705,1849,8239,15134,10896,1647,29534,27992,13767,3925,10316,29167,1823,8759,28195,27444,26673,4255,1365,14498,6173,17528,31280,5918,31428,627,28082,5757,18487,11178,24734,2119,20590,17028,13519,19386,10046,14040,22733,6930,19589,15701,20894,15880,9384,13857,5855,17817,21823,26304,29971,13576,23054,2872,27194,15398,26168,626,12454,26321,26031,6628,27658,26043,13039,15469,11476,21613,21740,2176,15804,8331,22856,4485,28573,30297,7882,20604,22404,22142,9228,2020,13063,14600,11891,7899,26329,25009,23908,14214,19355,18784,32181,1203,15604,16627,12642,8893,7907,12604,16258,30640,19796,7241,8313,24238,10738,17385,6766,8850,15421,6507,512,3026,6108,23209,29492,1450,32052,70,5810,7799,26681,24883,18226,26465,388,12152,11057,30524,9639,12849,5864,5296,30397,24790,19070,19352,11333,17344,24701,29097,5424,15849,131,24148,56,9204,10810,23021,32372,17517,11401,2060,13353,17745,7436,20788,11236,31441,25538,4018,24517,6995,12038,968,27934,29882,25537,21259,9789,1767,24029,5898,30341,10111,5373,16176,19652,4847,31083,18924,32704,3758,7505,6414,24851,194,32301,25973,29241,8326,639,5607,28648,9386,32708,32064,10143,4731,23720,17359,19330,4709,9080,32765,14437,28086,6358,16943,25127,6564,10928,6126,23105,29586,19315,19014,9374,4751,3451,23403,20142,21024,4815,1955,31926,31295,9483,19807,24938,10403,2461,16555,21437,24386,26164,11721,30456,23573,18806,20249,10505,7707,11250,6717,11038,15264,32085,26745,14451,28095,4576,32352,32616,29990,1049,13997,12503,15385,24257,21615,6564,22970,8967,16489,31382,23175,32507,13752,4709,29220,18501,8630,3604,31323,3863,15135,21376,25441,23904,5234,23098,31066,30275,11674,1682,8992,10695,18638,15092,32320,4304,1718,4984,31814,17742,3535,32692,25915,27316,16656,11989,25451,6828,18894,494,31852,2568,30941,30863,7003,31228,17144,19354,4201,18827,23650,10834,10646,15168,14286,19893,18621,17182,27773,22028,6865,28889,18342,9920,21606,19015,3354,13423,6003,10769,11048,31039,26198,30382,26046,882,18456,17810,15570,21051,499,16034,4608,29904,2577,21484,20853,8129,6039,8597,8715,11400,29666,2578,24757,14177,28944,25243,27422,20316,10691,17373,32141,27824,28193,21232,10252,8530,544,5768,7881,14278,4352,11375,27068,13366,31257,29491,14218,27585,23254,31772,22442,9749,31234,22880,8134,32064,30786,7322,16484,28611,27107,6521,19653,22760,15830,16565,31245,17238,5625,10056,22949,18915,29849,3546,4830,31401,25396,31869,24535,28764,30339,18074,20896,5595,21431,2859,8095,18436,6916,1323,1587,18893,23388,16459,30872,16016,29565,1511,10763,7847,1069,5688,12846,23097,22468,459,20653,7763,25324,14130,5154,28731,17061,6393,26678,4865,23436,12252,20233,27478,32348,19766,18901,21921,13749,12733,13518,8784,8476,3181,6732,11372,324,26050,16683,15985,22923,19242,31346,14684,19144,20154,29236,12805,2884,12064,1972,30895,8198,15321,28876,16094,15188,18852,11408,20329,25718,19254,2350,3279,19645,25135,16665,10702,30148,31821,29542,20530,3318,20703,31606,10732,8272,21117,27605,99,4200,26871,12386,26127,25519,1931,7088,7747,24307,29531,25517,14154,1832,19998,20865,2742,28775,14613,10425,6133,32311,9280,2469,27941,30988,7635,21246,4649,7437,13796,18124,10749,1562,19046,30343,15942,7438,20314,14973,26926,27201,26436,14451,20846,29010,24540,15759,11436,31267,26375,28534,15368,27428,3077,6321,30450,6357,24812,5205,22590,11910,20565,7395,378,5217,31573,621,10367,30379,13231,3066,838,21063,26183,2092,9725,10876,2522,20768,1882,19448,26093,18326,7984,16660,17923,2386,21312,23385,27923,26306,9809,30275,23865,23520,23939,22342,18348,4186,4064,20239,14576,8944,21556,12,21837,17438,286,28206,14719,25596,13160,15342,21423,30562,3732,14478,18594,6223,27575,9121,14641,1420,27275,18893,31737,17804,6335,24272,8019,28823,9105,14529,18311,26152,18335,20632,15676,29075,29434,11249,16435,8682,19837,5133,29237,22818,7005,15898,28234,22130,11776,18612,24620,16380,22291,12971,12283,28591,4567,12039,5682,1900,22203,31305,11226,4199,19760,5364,19198,10705,20409,1868,21342,2740,30273,4702,10087,23326,6834,29248,30051,10369,3011,5530,8430,31066,25106,28261,24745,17425,11122,16371,25650,19744,24710,3632,5715,12408,22671,4647,20345,6688,12162,22472,3176,29216,21086,26856,32046,32669,9660,10633,85,18245,31399,18780,24157,10478,17839,28292,22890,121,19513,32157,25913,19965,15385,8957,7000,10530,24931,313,16279,970,28285,10475,26810,32759,2681,15795,8560,23785,6562,27772,5513,16262,29781,5889,8035,23039,19,22671,18853,14001,24275,18444,6448,10825,10397,6968,13139,12588,25428,3891,13374,15382,11476,14912,18874,12288,19261,10952,26135,7496,6029,30626,8037,29196,30325,9617,3815,11222,21349,1550,17604,19583,20970,29512,9216,5709,10553,3434,15019,21343,24076,23836,27224,11339,20140,32588,29905,20997,17743,15918,16649,32515,1189,15233,27730,5022,686,4117,31696,20924,17870,1162,16942,31660,6179,18266,19855,23121,1302,17434,29128,28291,21808,32764,17100,20914,31792,8089,4967,2508,11610,31213,19504,21601,2577,23715,11961,11526,7848,26003,22792,4855,8566,5514,7499,20992,10280,73,455,21149,18267,15824,32018,13664,20587,220,17026,15763,8581,30382,13029,20255,15364,21518,17778,940,5370,13200,32000,6922,21516,10518,15734,19151,29828,11926,5507,12610,31905,19997,20623,28536,16177,11540,25841,11965,23394,23747,4706,5430,28374,5139,17585,28100,11765,13976,3769,1834,22151,19662,20881,3699,12418,20899,25602,26766,4384,31030,20030,20284,5173,21727,28110,13612,32704,30831,5581,13667,1472,1209,32596,4578,22601,15185,7733,1411,17366,32659,11756,27941,17377,26855,2770,3080,17841,19012,11156,28538,3444,21235,20196,13748,29069,11414,12654,15359,24623,14952,24590,30747,25387,24006,31296,224,5638,25583,30936,2598,16975,264,19699,22499,5679,31843,27437,27795,10562,29184,5908,30429,17317,19796,733,17011,6993,24906,5974,12346,31655,16776,30748,31147,2891,16627,6158,17273,9270,14709,29185,17267,29191,254,14774,32173,19098,12232,6409,23770,29916,7136,19818,10749,20958,11746,14737,10049,7208,29443,16238,21028,12623,4181,30303,4315,6602,31559,4518,20210,17153,7019,2842,19764,8103,14717,26140,10442,8778,24480,7885,23975,17960,3818,6527,18467,6725,28195,9833,27109,698,21962,28062,30215,9296,23897,22336,26741,11853,19915,17392,11414,30350,7514,10634,5935,7126,22669,26639,14212,8806,7282,27363,17344,16078,1576,27193,9366,17154,15265,24779,25641,25008,29094,2510,1065,15313,4892,31525,32575,27775,28037,12245,31148,1798,1738,5817,25901,15165,55,31095,7201,5143,10951,20402,14317,1141,12450,21121,9888,13886,30692,25632,17363};
    }
}
